package junior.DynamicProgramming动态规划;

/**
 * 一次爬 1 阶或者3阶
 */
public class 猴子爬山 {
    public static void main(String[] args) {
        int steps = 30;
        System.out.println("solutionA："+solutionA(steps));
        System.out.println("solutionB："+solutionB(steps));
        System.out.println("solutionC："+solutionBOptimization1(steps));
    }
    // 递归写法
    static long solutionA(int steps){
        if(steps == 1 || steps == 2)
            return 1;
        else if(steps == 3)
            return 2;
        else
            return solutionA(steps-1) + solutionA(steps-3);
    }
    // 动态规划，dp打表（递推写法）
    static long solutionB(int steps){
        long[] dp = new long[steps+1];
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        for (int i = 4; i <= steps; i++) {
            dp[i] = dp[i-1] + dp[i-3];
        }
        return dp[steps];
    }
    // 非递归优化写法(一维dp表，根据性质用变量更换)，时间未变，空间优化
    static long solutionBOptimization1(int steps){
        long first = 1, second = 2, last = 0;
        for (int i = 4; i <= steps; i++) {
            last = first + second;
            first = second;
            second = last;
        }
        return last;
    }
}
